>

Title: An Extension of the Prelle-Singer Method and a Maple Implementation

by L.G.S. Duarte, S.E.S. Duarte, L.A.C.P. da Mota and J.E.F. Skea

Universidade do Estado do Rio de Janeiro (UERJ), Brazil,

email: lduarte@dft.if.uerj.br, eduarte@cbpf.br, damota@dft.if.uerj.br and jimsk@dft.if.uerj.br,

November, 22, 2001

The Prelle-Singer method is a semi-decision algorithm which can be used to solve analytically first order ordinary differential equations (FOODEs) which have solutions in terms of elementary functions. Here we present a software package in MapleV Release 5 (as far as we could test, it works on release 7 as well) which implements both the Prelle-Singer method in its original form and an extension of our own which deals with first order ordinary differential equations whose solutions lie outside the scope of the standard method.
The results presented here are extracted from "L.G.S. Duarte, S.E.S. Duarte, L.A.C.P. da Mota and J.E.F. Skea, An Extension of the Prelle-Singer Method and a Maple Implementation " in press on Computer Physics Communications. From now on we will reffer to that paper as [cpc].

Introduction:

Before actualy introducing the ideas concerning our program, let us first load it to the Maple section. (Please, put the library file into directory `c:/DirectoryWhereIputtheLibrary`).

> restart;libname := `c:/DirectoryWhereIputtheLibrary`,libname;

> with(PSsolver);

Warning, these names have been redefined: Darboux, EigenPval, PSBasis, PSIntFac, Signature, polygen

>

The problem of solving ordinary differential equations (ODEs) has led, over the years, to a wide range of different methods for their solution. Along with the many techniques for calculating tricky integrals, these often occupy a large part of the mathematics syllabuses of university courses in applied mathematics round the world. The layman often imagines that behind computer algebra systems lies a large collection of freshman tricks and techniques laboriously executed one by one until the correct solution method is hit on. Computer algebra systems are `good at doing integrals' because they are faster than humans at trying all these techniques. Though, for reasons of speed, heuristic pattern-matching techniques are tried initially by most computer algebra systems, it comes as a surprise that the best computer algebra integration packages, when all else fails, use one fall-back method --- the Risch algorithm [2] . Given an integral the Risch algorithm tells you (in a finite time) what the integral is in terms of elementary functions, if such an expression exists. If the algorithm `fails', it is because no such closed-form solution exists and the user can be content that no matter how many books of tables of integrals he or she hunts in, the solution is not lurking in some dusty corner of the library. The Risch algorithm is based on the fact that, if the solution is elementary, we know its general form. It's just a matter of calculating the correct combinations of functions, coefficients and powers that appear. If we also know a limit on the degrees to which these functions can appear in the solution (a degree bound), then we can guarantee that a closed form integral does not exist if all possible combinations up to this degree have been exhausted. It is the existence of this degree bound in Risch's method that provides a fail safe terminating condition and turns the method into an algorithm. The situation with ODEs is more complicated. One can regard the problem of the analytic solution of an integral as a sub class of the problem of solving ODEs analytically. One might then hope that the techniques used in the Risch algorithm would also be applicable to ODEs. Unfortunately life is never that simple. However a big step forward in constructing an algorithm for solving first order ODEs (FOODEs) analytically was taken in a seminal paper by Prelle and Singer (PS) [3] on autonomous systems of ODEs. Prelle and Singer's problem is equivalent to asking when a FOODE of the form y'=M(x,y)/N(x,y) , with M and N polynomials in their arguments, has an elementary solution (a solution which can be written in terms of a combination of polynomials, logarithms, exponentials and radicals). Prelle and Singer were not exactly able to construct an algorithm for solving their problem, since they were not able to define a degree bound for the polynomials which might enter into the solution. Though this is important from a theoretical point of view, any computer implementation of the PS method will have a practical degree bound imposed by the processing speed and/or memory needed to handle the ever-more complex equations. With this in mind it is possible to say that Prelle and Singer's original method is almost an algorithm, awaiting a theoretical degree bound to turn it algorithmic. The purpose here is to present an extension to the Prelle-Singer method allowing for the solution of some FOODEs whose solutions contain a certain sub class of (non-elementary) Liouvillian functions (this sub class includes the error function).

The Prelle-Singer Method

Despite its usefulness in solving FOODEs, the Prelle-Singer procedure is not very well known outside mathematical circles, and so we present
a brief overview of the main ideas of the procedure.

Rational FOODEs :

Consider the class of FOODEs which can be written as:

y' = dy/dx = M(x,y)/N(x,y) (1)

where M(x,y) and N(x,y) are polynomials with coefficients in the field of complex numbers, C.

In [3] , Prelle and Singer proved that, if an elementary first integral of (1) exists, it is possible to find an integrating factor with in C[x,y] (the ring of polynomials over x and y with complex coefficients) for some integer n, such that

= 0 (2)

The ODE can then be solved by quadrature. From (2) we see that

(3)

Thus

(4)

where

(5)

Letting

(6)

where are irreducible polynomials and are non-zero rational numbers, we have from (5)

(7)

From (4) , plus the fact that M and N are polynomials, we conclude that is a polynomial. Therefore, from (7) , we see that must divide . We thus have a criterion for finding candidates for . Then, using (4) and (7) , we must have that

= (8)

If we can find a set of and which solve (8) , we can construct the integrating factor of the ODE and the solution of the ODE is reduced to a quadrature. Risch's algorithm [2] can then be applied to this quadrature to determine whether a solution exists in terms of elementary functions. Written in the form \

= , (9)

for some polynomial , we see that the equation for the has aspects similar to an eigenvalue equation, and for that reason are sometimes called eigenpolynomials [6] . However current usage seems to prefer the term Darboux polynomials (DPs), and we shall refer to the as such.

Algebraic and Transcendental FOODEs

In the standard PS procedure described above it is assumed that the M(x,y) and N(x,y) which appear in [3] belong to C[x,y]. Of course, many FOODEs which we want to solve do not fall into this class. However Shtokhamer [4] has extended the PS method to cover FOODEs with transcendental functions (exponential and logarithmic functions of the variables, with complex coefficients) and algebraic terms. To allow the PS method to treat transcendental and algebraic terms appearing in M(x,y) and N(x,y), the original variables of the ODE are initially supplemented by a basis of potentially independent functions ( , ,..., ) which appear in the ODE. A new function is considered potentially independent if it is not a rational power of an element already in U. Therefore = sin(x) and = cos(x) are considered potentially independent functions for the purposes of constructing U , even though they are algebraically dependent via the relation = 1- .

Since part of the PS method depends on the construction of polynomials in the , any implementation of the PS method must take into account this algebraic dependence at some point. Of course, if this recognition of the dependence fails, the implementation of the PS-approach can not assure to find the integrating factor up to the order considered. So, we can only assure that our program will find integrating factors of given degrees provided that no such dependencies are missed. For details please see [4] and [cpc].

An Extension To the Prelle-Singer Method

Our aim in this section is to offer a brief introduction to the ideas behind an extension to the Prelle-Singer method [1,8] which increases its scope of applicability to FOODEs with a class of non-elementary solutions.

As has been mentioned, given sufficient time, the standard PS method guarantees to find a solution for a FOODE of the form y'=M(x,y)/N(x,y) ( M and N polynomials in their arguments) if this solution is expressible in terms of elementary functions. However the method can also be used to solve some FOODEs whose solutions are not elementary. The question therefore arises of what distinguishes those FOODEs with non-elementary solutions which are solvable by the PS method from those that are not. In what follows we study this question and show how this allows us to extend the class of equations solvable by the PS method.

The following two ODEs are examples I.211 and I.21 respectively of the standard testing ground for ODE solvers by Kamke [5]

(10)

and

(11)

These ODEs have, respectively, the general solutions

, (12)

and

. (13)

We note that neither solution is expressible in terms of elementary functions. However, in the case of FOODE (10) , the PS method can be used to find the solution (12) while the same is not true for FOODE (11) . To find out why, we look at the integrating factor, R , for the ODEs which are, respectively,

(14)

and

. (15)

In both cases R is a product of elementary functions, which we may write as

(16)

For (10) the set of elementary functions is { } , while for (11) this set is { , } . Now the in (16) are all polynomials over the building blocks which appear in the ODE (10) , but this is not the case for (11) . Since the standard PS procedure constructs integrating factor candidates from polynomials, algebraic functions and logarithms in the functions which appear in the ODE, exponentials of the type that appears in the factor are never considered and the solution to (11) eludes the standard PS method. However the above discussion points the way to a method which extends the original PS procedure to deal with cases similar to (11) . This method is fully explained in [cpc] and [7].

PSsolver Package Summary and Examples

Summary

A brief sumary of the commands of the package is as follows:

PSsolve - solves FOODEs using the Prelle-Singer approach. In addition to dealing with rational FOODEs (the scope of the standard PS procedure), it also deals with FOODEs which contain elementary (algebraic and transcendental) functions.

PSIntFac - returns an integrating factor for the FOODE.

PSDop - constructs the D operator associated with the FOODE.

PSBasis - builds a list of equations which define the basis of potentially independent functions, = f(x,y), ... , used to construct the integrating factor for the FOODE.
dPSBasis - calculates the list of partial derivatives of the basis of potentially independent functions (e.g., ) .
Darboux - calculates the DPs, i.e. the polynomials satisfying D = .
PSEigenval - calculates the polynomials that are the ``eigenvalues'' for the equation D = .

A complete description of the commands in the PSsolver package is available in the on-line help. Please note that the on-line help must be installed according to the instructions found on readme.mws. Here we have described the commands that are implemented.

Examples

> eq := diff(y(x),x) = y(x)^2*(y(x)^2*ln(x)^5+4*y(x)*ln(x)^3+4*ln(x)+y(x)^2)/((y(x)*ln(x)^2+2)^2*x);

> dsolve(eq);

> PSIntFac(eq,1);

> PSsolve(eq,1);

> eq := diff(y(x),x) = (-cos(x)*x*y(x)-cos(x)*x-cos(x)*1+y(x)+1+x*exp(y(x)))/(1+x*y(x));

> dsolve(eq);

> PSIntFac(eq,1,Extended);

> PSsolve(eq,1,Extended);

Bibliography

[1] - M. Singer, Liouvillian First Integrals of Differential Equations, Trans. Amer. Math. Soc., 333 , 673--688 (1992).

[2] - R.H. Risch, The Problem of Integration in Finite Terms, Trans. Amer. Math. Soc ., 139 , 167--189, (1969).

[3] - M. Prelle and M. Singer, Elementary first integrals of differential equations, Trans. Amer. Math. Sol. , 279, 215, (1983).

[4] - R. Shtokhamer, Solving first order differential equations using the Prelle-Singer algorithm , Technical report 88-09 , Center for Mathematical Computation, University of Delaware (1988).

[5] E. Kamke, Differentialgleichungen: Lösungsmethoden und Lösungen . Chelsea Publishing Co, New York (1959).

[6] - Y.K. Man and M.A.H. MacCallum, A Rational Approach to the Prelle-Singer Algorithm. J. Symbolic Computatio, 11 , 1--11 (1996)

[7] - L.G.S. Duarte, S.E.S. Duarte, L.A.C.P. da Mota and J.E.F. Skea, Analyzing the Structure of the Integrating Factors for First Order Ordinary Differential Equations with Liouvillian Functions in the Solution ., in Press on J. Phys. A: Mathematical, Nuclear and General.

[8] - L.G.S. Duarte, S.E.S. Duarte, L.A.C.P. da Mota and J.E.F. Skea, A Method to Tackle First Order Ordinary Differential Equations with Liouvillian Functions in the Solution , submitted to J. Phys. A: Mathematical, Nuclear and General.

Conclusion:

The aim here has been to present the computer package PSsolver which, as well as implementing the Prelle-Singer method for solving first order ODEs, includes the implementation of an extension to the method also described in the paper, which allows for the solutions of some FOODEs with non-elementary solutions. The PS method is radically different from other solution methods in that it is almost algorithmic and applicable to any FOODE which has a solution in terms of elementary functions, regardless of the form of the ODE . To help study the PS procedure in action, PSsolver comes with a set of commands which allow the user to study all the intermediate steps of the PS-procedure, from the construction of the basis of potentially independent functions and the D operator to the calculation of the DPs and the building of the integrating factor. Because of its different approach we would expect that the PS method solves FOODEs which elude other solvers. In our case the natural comparison is with Maple's standard ODE solver, dsolve , and the results based on an independent test suite confirm that PSsolver does, indeed, solve ODEs where dsolve fails. In summary, since we believe the PS-method to be a very (for the reasons just pointed out) attractive approach to solving ODEs, we have decided to improve it further, by creating a algorithm allowing it to tackle a wider range of ODEs. Furthermore, by implementing this new algorithm and the usual PS-method in Maple, our package allows Maple to solve ODEs previously missed by its own in-house solver. As further development of this work, we are currently working on extensions to the package to tackle FOODEs containing arbitrary functions, and on the implementation of the Collins approach (see [6] and references therein) to the PS procedure, which we hope will make the program even more efficient.

Disclaimer: While every effort has been made to validate the solutions in this worksheet, Waterloo Maple Inc. and the contributors are not responsible for any errors contained and are not liable for any damages resulting from the use of this material.